//二叉树翻转，按层进行翻转，将所有左子树变成右子树
//可以使用递归（每层进行）或者迭代的方法（在进行深度遍历时也有这个思路），还可以用层序遍历的方式进行（辅助队列）
#include <stack>
#include <queue>
using namespace std;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};


//递归法
TreeNode* invertTree_recursion(TreeNode* root)
{
    if(!root) return root;
    swap(root->left,root->right);
    if(root->left) invertTree_recursion(root->left);
    if(root->right) invertTree_recursion(root->right);
    return root;

}

//迭代法——使用栈来模拟递归过程
TreeNode* invertTree_stack(TreeNode* root)
{
    if(!root) return root;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* node=st.top();
        st.pop();
        swap(node->left,node->right);
        //翻转完毕进行压栈，下次while循环执行的就是压入栈的内容，相当于递归的实现
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }
    return root;
}

//迭代法——使用队列来实现
TreeNode* invertTree_queue(TreeNode* root)
{
    if(!root) return root;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty())
    {
        int size=que.size();
        for(int i=0;i<size;i++) //按一层里的每个结点进行翻转
        {
            TreeNode* node=que.front();
            que.pop();
            swap(node->left,node->right);
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
    }
    return root;
}